package com.xiayuanxing.arithmetic.DataStructures.Tree;

/**
 * @program: arithmetic
 * @description: 线索化二叉树
 * @author: xia yuan xing
 * @create: 2021-10-07 14:43
 */
public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {

        //测试
        HeroNodel root = new HeroNodel(1, "tom");
        HeroNodel node2 = new HeroNodel(3, "jack");
        HeroNodel node3 = new HeroNodel(6, "smith");
        HeroNodel node4 = new HeroNodel(8, "mary");
        HeroNodel node5 = new HeroNodel(10, "king");
        HeroNodel node6 = new HeroNodel(14, "dim");

        //手动创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        //测试中线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();

        System.out.println("十号节点的前驱节点：  "+node5.getLeft().toString());
        System.out.println("十号节点的后继节点：  "+node5.getRight().toString());

        threadedBinaryTree.threadedList();

    }
}


/**
 * 定义实现了线索化功能的二叉树
 */
class ThreadedBinaryTree{

    private HeroNodel root;

    //当前节点指向前驱节点的引用 在递归进行线索化时，总是保留前一个节点
    private HeroNodel pre = null;

    public void setRoot(HeroNodel root) {
        this.root = root;
    }

    /**
     * 重载
     */
    public void threadedNodes(){
        this.threadedNodes(root);
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        if (this.root != null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空，无法遍历！");
        }
    }


    /**
     * 前序查找
     * @param no
     * @return
     */
    public HeroNodel preOrderSearch(int no){
        if (root != null){
            return root.preOrderSearch(no);
        }else {
            System.out.println("二叉树为空，无法查找！");
            return null;
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (this.root != null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历！");
        }
    }


    /**
     * 中序查找
     * @param no
     * @return
     */
    public HeroNodel infixOrderSearch(int no){
        if (root != null){
            return root.infixOrderSearch(no);
        }else {
            System.out.println("二叉树为空，无法查找！");
            return null;
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        if (this.root != null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历！");
        }
    }


    /**
     * 后序查找
     * @param no
     * @return
     */
    public HeroNodel postOrderSearch(int no){
        if (root != null){
            return root.postOrderSearch(no);
        }else {
            System.out.println("二叉树为空，无法查找！");
            return null;
        }
    }


    /**
     * 删除节点
     * @param no
     */
    public void deleteNode(int no){
        if (root != null){

            //如果只有一个节点
            if (root.getNo() == no){
                root = null;
                return;
            }else {
                //递归删除
                root.deleteNodel(no);
            }

        }else {
            System.out.println("空二叉树，不能删除！");
        }
    }


    /**
     * 中序线索化
     * @param heroNodel 当前需要线索化的节点
     */
    public void threadedNodes(HeroNodel heroNodel){

        //非空校验
        if (heroNodel == null){
            return;
        }
        //先线索化左子树
        threadedNodes(heroNodel.getLeft());

        //线索化当前节点
        //先处理当前节点的前驱节点
        if (heroNodel.getLeft() == null){
            //让当前节点的左指针指向前驱节点
            heroNodel.setLeft(pre);
            //修改当前节点的左指针类型
            heroNodel.setLeftType(1);
        }

        //处理当前节点的后继节点
        if (pre != null && pre.getRight() == null){
            pre.setRight(heroNodel);
            pre.setRightType(1);
        }

        //每处理一个节点后。让当前节点变成下一个节点的前驱节点
        pre = heroNodel;

        //线索化右子树
        threadedNodes(heroNodel.getRight());
    }


    /**
     * 遍历中序线索化二叉树
     */
    public void threadedList(){
        HeroNodel node  = root;
        while (node != null){
            //循环的找到leftType == 1 的节点，第一个找到的就是8节点
            //后面随着遍历而变化，当leftType == 1时，说明该节点是按照线索化
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            //打印当前节点
            System.out.println(node);

            //如果当前节点的右指针指向的是后继节点，就一直输出
            while (node.getRightType() == 1){
                node =  node.getRight();
                System.out.println(node);
            }

            //替换遍历节点
            node = node.getRight();

        }

    }

}




/**
 * HeroNode节点
 */
class HeroNodel{
    private int no;
    private String name;
    private HeroNodel left;
    private HeroNodel right;
    //==0 指向左子树  ==1 指向前驱节点
    private int leftType;
    //==0 指向右子树  ==1 指向后继节点
    private int rightType;

    public HeroNodel(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNodel getLeft() {
        return left;
    }

    public void setLeft(HeroNodel left) {
        this.left = left;
    }

    public HeroNodel getRight() {
        return right;
    }

    public void setRight(HeroNodel right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNodel{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }


    /**
     * 前序遍历
     */
    public void preOrder(){
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left != null){
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null){
            this.right.preOrder();
        }
    }


    /**
     * 前序查找
     * @param no 查找的no
     * @return 如果找到就返回节点，找不到就返回null
     */
    public HeroNodel preOrderSearch(int no){
        //比较当前节点是不是要查找的节点
        if (this.no == no){
            return this;
        }
        //判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
        HeroNodel heroNodel = null;
        if (this.left != null){
            heroNodel = this.left.preOrderSearch(no);
        }
        //说明左子节点找到了
        if (heroNodel != null){
            return heroNodel;
        }
        //否则判断右子节点
        if (this.right != null){
            heroNodel = this.right.preOrderSearch(no);
        }
        return heroNodel;
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        //递归向左子树前序遍历
        if (this.left != null){
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right != null){
            this.right.infixOrder();
        }
    }


    /**
     * 中序查找
     * @param no 查找的no
     * @return 如果找到就返回节点，找不到就返回null
     */
    public HeroNodel infixOrderSearch(int no){
        HeroNodel heroNodel = null;
        if (this.left != null){
            heroNodel = this.left.infixOrderSearch(no);
        }
        //说明左子节点找到了
        if (heroNodel != null){
            return heroNodel;
        }
        if (this.no == no){
            return this;
        }

        //否则判断右子节点
        if (this.right != null){
            heroNodel = this.right.infixOrderSearch(no);
        }
        return heroNodel;
    }


    /**
     * 后序遍历
     */
    public void postOrder(){
        //递归向左子树前序遍历
        if (this.left != null){
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null){
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }


    /**
     * 后序查找
     * @param no 查找的no
     * @return 如果找到就返回节点，找不到就返回null
     */
    public HeroNodel postOrderSearch(int no){
        HeroNodel heroNodel = null;
        if (this.left != null){
            heroNodel = this.left.postOrderSearch(no);
        }
        //说明左子节点找到了
        if (heroNodel != null){
            return heroNodel;
        }

        //否则判断右子节点
        if (this.right != null){
            heroNodel = this.right.postOrderSearch(no);
        }

        //说明右子节点找到了
        if (heroNodel != null){
            return heroNodel;
        }

        if (this.no == no){
            return this;
        }
        return heroNodel;
    }


    /**
     * 删除节点
     * 1.如果删除的节点是叶子节点，则删除该节点
     * 2.如果删除的节点是非叶子节点，则删除该子树
     * @param no
     */
    public void deleteNodel(int no){

        /**
         * 思路：
         * 1.因为二叉树是单向的，所以我们判断当前节点的子节点是否需要删除，而不能判断当前的这个节点是不是要删除、
         * 2.如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left==null,结束递归删除
         * 3.如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right==null,结束递归删除
         * 4.如果第二步和第三步没有删除节点，那么我们就需要向左子树进行递归删除
         * 5.如果第四部也没有删除节点，则应当向柚子树进行递归删除
         */

        //2.如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left==null,结束递归删除
        if (this.left != null && this.left.no == no){
            this.left = null;
            return;
        }


        //3.如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right==null,结束递归删除
        if (this.right != null && this.right.no == no){
            this.right = null;
            return;
        }

        //4.向左子树进行递归删除
        if (this.left != null){
            this.left.deleteNodel(no);
        }

        //5.向右子树进行递归删除
        if (this.right != null){
            this.right.deleteNodel(no);
        }
    }

}